import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/**
 * 20. Valid Parentheses 有效的括号
 * https://leetcode.com/problems/valid-parentheses/
 */
class ValidParentheses {
    /**
     * 方法：使用栈来验证括号的有效性
     * 
     * Args:
     *   s: 包含括号的字符串
     * 
     * Returns:
     *   boolean: 如果括号有效返回true，否则返回false
     * 
     * Time: O(n) - 需要遍历整个字符串
     * Space: O(n) - 最坏情况下栈的大小为n/2
     */
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 != 0){
            return false;
        }
        Map<Character, Character> mp = new HashMap<>(){{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> st = new ArrayDeque<>();
        for(Character c : s.toCharArray()){
            if(!mp.containsKey(c)){ // c是左括号
                st.push(c); //入栈
            }else if(st.isEmpty() || st.pop() != mp.get(c)){ // c 是右括号
                return false; // 没有左括号，或者左括号类型不对
            }
        }
        return st.isEmpty(); // 所有左括号必须匹配完毕
    }
}